function binarySerach(arr: number[], target: number): number {
  const len = arr.length
  let startIndex = 0
  let endIndex = len - 1
  if (len === 0) return -1
  // 开始循环
  while (startIndex <= endIndex) {
    let midIndex = Math.floor((endIndex + startIndex) / 2)
    let midValue = arr[midIndex]
    // 大于往右边查找
    if (target > midValue) {
      startIndex = midIndex + 1
    } else if (target < midValue) {
      // 小于往左查找
      endIndex = midIndex - 1
    } else {
      return midIndex
    }
  }
  return -1
}

function binarySerach1 (arr: number[], target: number, startIndex?: number, endIndex?: number): number {
  const len = arr.length
  if (len === 0) return -1
  // 开始和结束的范围
  if (startIndex == null) startIndex = 0
  if (endIndex == null) endIndex = len -1
  // 相遇就结束
  if (startIndex > endIndex ) return -1

  // 中间位置
  const midIndex = Math.floor( (startIndex + endIndex) / 2 )
  const midValue = arr[midIndex]
  if (target > midValue) {
    return binarySerach1(arr, target, midIndex + 1, endIndex)
  } else if (target < midValue) {
    return binarySerach1(arr, target, startIndex, midIndex - 1)
  } else {
    return midIndex
  }
}
const arr = [1,3,4,5,6,7,8,9]
console.info(binarySerach1(arr, 100 ))
export {
  binarySerach
} 